1. Field of the Invention
The present invention generally relates to wireless communication systems and, more particularly, to a scheduling method that gives high system throughput and fairness among different connections in a wireless network.
2. Background Description
Most of the emerging pico-cellular wireless communication systems are Master driven Time Division Duplex (TDD) based systems. Conventional data packet scheduling strategies based on a Round Robin scheduling protocol perform poorly in these systems.
The physical constraints of the wireless medium often lead naturally to a Master-Slave configuration. In a Master-Slave configuration, one of the stations in a cell is the Master (this could be a fixed Access Point or a Base Station) and the other remote stations are Slaves (e.g., the handheld devices such as palmtop computers, cell phones, pagers).
The need for simplicity and low complexity has made Time Division Duplex (TDD) one of the promising candidates for medium access control (MAC) in wireless systems having a Master-Slave configuration. In TDD MAC, the forward (i.e., Master to Slave) and the reverse (i.e., Slave to Master) slots occur in pairs; that is, once data is sent by the Master in the forward slot, the subsequent slot is reserved for the Slave to transmit data, as illustrated in FIG. 1. Further, the asymmetry of base stations and mobile units and the resource scarcity at mobile units make it desirable in wireless systems to have most of the complexity at the Master. This mode of operation makes multiple access straight forward, since the Master provides a single point of coordination. Proposed standards for low-power, low-cost wireless mobile communication systems have adopted centralized TDD scheduling as the MAC protocol for scheduling access to the wireless medium.
Master driven TDD scheduling poses several challenges since the traditional scheduling policies do not perform well over this kind of a MAC. Once a Master polls a Slave, the next slot is reserved for the Slave irrespective of whether the Slave has data to send or not (see again FIG. 1). An efficient scheduling methodology would depend upon (i) the state of the queues at the Master and at the Slaves, (ii) the traffic arrival process at these queues, and (iii) the packet length distribution at the Master and the Slave. It is with this in mind that we propose a new scheduling method adapted for TDD MAC at the Master. The parameters of interest that we have studied are (i) system throughput, (ii) packet delays and (iii) fairness. Throughput is defined as number of slots utilized for transmitting data. Fairness is defined as equal bandwidth for different connections.
Scheduling methods which involve a-priori reservation of slots by the slaves have been proposed. See for example, U.S. Pat. No. 5,506,848 to Drakopoulos et al. for xe2x80x9cDemand Assignment System and Method for Mobile Users in a Community of Interest xe2x80x9d. However, in some systems, reservation of slots for data packets is not allowed. Due to the Master driven TDD structure, a Slave packet can only be transmitted after a Master packet.
In U.S. Pat. No. 5,274,841 to Natarajan et al. for xe2x80x9cMethods for Polling Mobile Users in a Multiple Cell Wireless Network xe2x80x9d, methods for polling mobile users have been discussed. However, the uplink wireless communication is done using CSMA (Carrier Sensing, Multiple Access) protocol.
A two stage non-contention based Multiple Access protocol is discussed in U.S. Pat. No. 5,297,144 to Gilbert et al. for xe2x80x9cReservation-based Polling Protocol for A Wireless Data Communications Network xe2x80x9d. This protocol is based on Reservation based polling. The slot restrictions in some systems make such an approach infeasible.
In U.S. Pat. No. 4,763,322 to Eizenhofer for xe2x80x9cDigital Radio Transmission System with Variable Duration Time Slots in the Time-Division Multiplex Frame xe2x80x9d, a scheduling method with variable duration of the time slots in the time-division multiplex frame is discussed. However, the methodology is not applicable to a TDD system and has variable duration time slots (as opposed to systems having fixed size slots).
A scheduling method for providing proportional use of network bandwidth is proposed in U.S. Pat. No. 5,844,890 to Delp et al. for xe2x80x9cCommunications Cell Scheduler and Scheduling Method for Providing Proportional Use of Network Bandwidth. However, this method is not suited to some systems as it does not tackle the issues posed by Master driven TDD systems.
In Master Driven TDD wireless systems, Master and Slave queues are served in pairs. If a Master has data to send and Slave has no data to send, the reverse slot is wasted, as illustrated in FIG. 2. In such systems, each Slave has a queue of data packets to be sent to the Master (we refer to this as the Slave queue from now onwards). Similarly, there is a queue at the Master for each Slave, containing data packets to be sent to the Slave.
We observe that different connections can have different slot utilization. To increase system throughput, we need to give more service to connections with less slot wastage. However, by doing so we are introducing unfairness (in terms of slots received by a connection) among different connections. We need scheduling methods that increase system throughput yet provide fairness. See, for example, C. Fragouli, V. Sivaraman and M. B. Srivastava; xe2x80x9cControlled Multimedia Wireless Link Sharing via Enhanced Class-Based Queueing and Channel-State-Dependent Packet Scheduling xe2x80x9d, IEEE INFOCOM ""98, San Franscisco, Calif., March, 1998; S. Lu, V. Bharghavan and R. Srikant, xe2x80x9cFair Scheduling in Wireless Packet Networks xe2x80x9d, ACM SIGCOMM ""97, August, 1997; and S. Lu, T. Nandagopal and V. Bharghavan, xe2x80x9cA Wireless Fair Service Algorithm for Packet Cellular Networks xe2x80x9d, ACM MOBICOM ""98, Dallas, Tex., 1998.
The conventional scheduling policies are based on Round Robin (RR) Scheduling. In RR scheduling, different connections are visited in a cyclic order. FIG. 3 illustrates the scenario in RR scheduling.
In TDD Master driven systems the scheduling is done in pairs of queues rather than a single queue (Forward slot for the Master queue followed by the Reverse slot for the Slave queue). Conventional strategies like Round-Robin scheduling will give equal slot allocation to all the connections. Since different connections have different slot utilization, this can lead to significant slot wastage in RR scheduling.
It is therefore an object of the present invention to provide a scheduling method that provides high throughput and at the same time fairness in Master driven TDD wireless systems.
The scheduling policies that we propose can be labeled as Master-Slave Queue-State-Dependent Packet Schedulihng Policies. These policies use the information about Master and Slave queues to achieve better system performance. The scheduling methodology is implemented at the Master and therefore has access to information about the Master queues. Different kinds of information about the queues such as backlog, size, delays can be used.
As an example, in our scheduling policies we use the xe2x80x9cbacklog xe2x80x9d information at the Master and Slave queues. A Queue is backlogged if it has packets to send. Denote by xe2x80x9c1xe2x80x9d the state in which a queue (Master or Slave) has data to send and by xe2x80x9c0xe2x80x9d when there is no data to send. Clearly, this leads to four distinct states of the Master-Slave queue pairs. For example, the Master-Slave xe2x80x9cpair xe2x80x9d is in the xe2x80x9c1-1xe2x80x9d state if both the Master and the Slave of a connection have data to send (are backlogged); if both Master and Slave have no data, this pair is in the xe2x80x9c0-0xe2x80x9d state.
The queue information about the Slaves can be communicated by various mechanisms to the Master. The communication may be through piggybacking information on packets or implicit mechanisms such as observing the system. In our policies, we convey the backlog information about the Slave queue to the Master by piggybacking a bit on the Slave to the Master packets, if any. This bit can be present in the headers or in the payload. For each packet the Slave sends, this bit is marked xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d. It is marked xe2x80x9c1xe2x80x9d if there are more outstanding packets in the queue and xe2x80x9c0xe2x80x9d if there is no backlog.